# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 20_get_best_gold_mining_R.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/2/10 15:19
------------------------------------------
    5座金矿，每个金矿的 金矿储量/需要的工人数量 分别为：
            400kg/5人,
            500kg/5人
            200kg/3人，
            300kg/4人，
            350kg/3人
    工人总共 10个，每座金矿只能选择不挖和全挖，
    问：挖那几座金矿能得到更多的黄金？

    关键词： 动态规划，类似背包问题

    动态规划：
        把复杂的问题简化成规模较小的子问题，
        再从简单的子问题自底向上一步一步递推，
        最终得到复杂问题的最优解

    通用公式：
    假设
        金矿数量为 n，工人数量为 w，
        金矿的含金量为数组 g[], 金矿所需开采人数设为数组 p[],
        F(n, w)为 n个金矿、w个工人时的最优收益函数，则

        ① 问题边界，金矿数为 0 或工人数为 0的情况
            F(n, w) = 0 (n = 0 或 w = 0)

        ② 当所剩工人不够挖当前金矿时，只有一种最优子结构
            F(n, w) = F(n - 1, w)(n ≥ 1,w < p[n -1])

        ③ 常规情况下，有两种最优子结构
            F(n, w)= max(F(n-1, w), F(n-1, w - p[n-1]) + g[n - 1]) ,(n ≥ 1,w ≥ p[n-1])

"""


def get_best_gold_mining(w, n, p=None, g=None):
    """
        基础版：这个有重复计算

        :param w: 工人数量
        :param n: 可选金矿数量
        :param p: 金矿开采所需工人数量
        :param g: 金矿储量
        :return: 最优收益
    """

    if p is None:
        p = []
    if g is None:
        g = []
    if w == 0 or n == 0:
        return 0

    if w < p[n - 1]:
        return get_best_gold_mining(w, n - 1, p, g)

    return max(get_best_gold_mining(w, n - 1, p, g))


def get_best_gold_mining_v2(w, n, p=None, g=None):
    """
        :param w: 工人数量
        :param n: 可选金矿数量
        :param p: 金矿开采所需工人数量
        :param g: 金矿储量
        :return: 最优收益
    """

    # 这里存储的是一张带一行和一列表头的计算结果表
    result_table = [[0 for _ in range(w + 1)] for _ in range(len(g) + 1)]

    # 填充表格
    for i in range(1, len(g) + 1):
        for j in range(1, w + 1):
            if j < p[n - 1]:
                result_table[i][j] = result_table[i - 1][j]

            else:
                result_table[i][j] = max(
                    result_table[i - 1][j],
                    result_table[i - 1][j - p[n - 1]] + g[i - 1]
                )

    # 返回最后一个格子的值
    return result_table[len(g)][w]


def get_best_gold_mining_v3(w, n, p=None, g=None):
    """
        优化了空间复杂度
        :param w: 工人数量
        :param n: 可选金矿数量
        :param p: 金矿开采所需工人数量
        :param g: 金矿储量
        :return: 最优收益
    """

    # 创建当前结果
    results = [0] * (w + 1)

    # 填充一维数组
    for i in range(1, len(g) + 1):
        for j in range(w, 0, -1):
            if j >= p[i - 1]:
                results[j] = max(results[j], results[j - p[i - 1]] + g[i - 1])

    # 返回最后一个格子的值
    return results[w]
